package com.LeeCode;

/**
 * K个一组翻转链表
 */

public class Code025 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int k = 2;

        ListNode head = Utils.arrayToListNode(arr);
        Utils.printListNode(new Code025().reverseKGroup1(head, k));
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummyHead = new ListNode();
        ListNode pre = dummyHead;
        dummyHead.next = head;

        ListNode tail = head;

        for (int i = 0; i < k; i++) {
            tail = tail.next;
        }

        ListNode[] fisrt = reserse(head, tail);
        dummyHead.next = fisrt[0];
        pre = fisrt[1];
        pre.next = tail;
        // pre 表示反转区域的前一个节点，tail表示反转区域的后一个节点
        while (tail != null) {
            head = tail;
            int i = 0;
            for (; i < k && tail != null; i++) {
                tail = tail.next;
            }
            if (i != k) {
                pre.next = head;
                break;
            }
            ListNode[] tmp = reserse(head, tail);
            pre.next = tmp[0];
            pre = tmp[1];
        }

        return dummyHead.next;
    }

    public ListNode[] reserse(ListNode head, ListNode tail) {
        if (head == null)
            return null;

        ListNode[] res = new ListNode[2];
        res[1] = head; // 反转后的尾指针
        ListNode pre = null, cur = head, tmp;
        while (cur != tail) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        res[0] = pre; // 反转后的头指针
        return res;
    }

    public ListNode reverseKGroup1(ListNode head, int k) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            n++;
        }

        ListNode dummyHead = new ListNode(0, head);
        ListNode p0 = dummyHead, pre = null;
        cur = p0.next;
        while (n >= k) {
            n -= k;
            for (int i = 0; i < k; i++) {
                ListNode nxt = cur.next;
                cur.next = pre;
                pre = cur;
                cur = nxt;
            }

            ListNode nxt = p0.next;
            p0.next.next = cur;
            p0.next = pre;
            p0 = nxt;
        }

        return dummyHead.next;
    }
}
